package com.platform.modules.alg.alglib.hdu3085;

import java.util.LinkedList;
import java.util.Queue;

public class Hdu3085 {
    public String output = "";

    private final int N = 805;
    private int n;
    private int m;
    private int step;
    private char mp[][] = new char[N][N];
    private int dir[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    node gg = new node();
    node mm = new node();
    node zz[] = new node[2];
    Queue<node> q[] = new Queue[2];

    public Hdu3085() {
        for (int i = 0; i < zz.length; i++) {
            zz[i] = new node();
        }
        for (int i = 0; i < q.length; i++) {
            q[i] = new LinkedList<>();
        }
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);

        for (int k = 0; k < n; k++) {
            String mapLine = line[k + 1];
            for (int j = 0; j < mapLine.length(); j++) {
                mp[k][j] = mapLine.charAt(j);
            }
            int cnt = 0;
            // 找出男/女/鬼的位置
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (mp[i][j] == 'Z') {
                        zz[cnt].x = i;
                        zz[cnt++].y = j;
                    }
                    if (mp[i][j] == 'M') {
                        mm.x = i;
                        mm.y = j;
                    }
                    if (mp[i][j] == 'G') {
                        gg.x = i;
                        gg.y = j;
                    }
                }
            }
        }
        output = "" + solve();
        return output;
    }

    boolean check(int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m || mp[x][y] == 'X') return false;
        for (int i = 0; i < 2; i++)
            if (Math.abs(x - zz[i].x) + Math.abs(y - zz[i].y) <= 2 * step) return false;
        return true;
    }

    boolean bfs(int t, int num, char st, char ed) {
        Queue<node> que = new LinkedList<node>();;
        que.addAll(q[t]); // 将 q[t] 内容复制到 que中
        for (int k = 0; k < num; k++) {
            while (!que.isEmpty()) {
                node now = que.peek();
                que.poll();
                q[t].poll();
                if (!check(now.x, now.y)) continue;
                for (int j = 0; j < 4; j++) {
                    int fx = now.x + dir[j][0];
                    int fy = now.y + dir[j][1];
                    if (!check(fx, fy) || mp[fx][fy] == st) continue;
                    if (mp[fx][fy] == ed)
                        return true;
                    mp[fx][fy] = st;
                    q[t].add(new node(fx, fy));
                }
            }
            que.addAll(q[t]); // 将 q[t] 内容复制到 que中
        }
        return false;
    }

    int solve() {
        while (!q[0].isEmpty()) q[0].poll();
        while (!q[1].isEmpty()) q[1].poll();
        q[0].add(mm);
        q[1].add(gg);
        step = 0;
        while (!q[0].isEmpty() && !q[1].isEmpty()) {
            step++;
            if (bfs(0, 3, 'M', 'G') || bfs(1, 1, 'G', 'M'))
                return step;
        }
        return -1;
    }
}

class node {
    public int x;
    public int y;

    node() {
    }

    node(int x_, int y_) {
        x = x_;
        y = y_;
    }
}
